#include"Stack.h"
#include<stdio.h>

void Swap(int *a,int*b)//交换
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void Printf(int*a,int n)
{
    for(int i =0;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
//int Address(int* a,int left,int right)//找key
//{
//    int key=left;
//    while(left<right)
//    {
//        while(left<right&&a[right]>=a[key])//如果righty位置的值大于key加加直到遇到小的或者遇到left
//        {
//            right--;
//        }
//        while(left<right&&a[left]<=a[key])
//        {
//            left++;
//        }
//        Swap(&a[left],&a[right]);
//    }
//    Swap(&a[key],&a[left]);//吧key换到他的专属位置
//    return left;
//}
//void QuickSort(int*a,int left ,int right)
//{
//    STK tail;
//    StackInit(&tail);//初始化
//
//    //先入末尾节点，先进后出
//    StackPush(&tail,right);
//    StackPush(&tail,left);
//
//
//    //[left key-1][key+1 right]
//    while(!CheckEmpty(&tail))//判断栈里面是否还有元素
//    {
//
//        StackPrint(&tail);
//        int began=StackTop(&tail);//取栈顶
//        StackPrint(&tail);
//        int end=StackTop(&tail);
//
//        int key =Address(a,began,end);//找key
//
//       if(end>began&&end!=0)//如果end为0或者began大于end代表都不需要交换了
//       {
//           //左半区间
//           StackPush(&tail,end);
//           StackPush(&tail,key+1);
//           //右半区间
//           StackPush(&tail,key-1);
//           StackPush(&tail,began);
//       }
//    }
//
//    StackDestroy(&tail);//销毁
//}

//void _MergeSort(int *a,int *tmp,int left ,int right)//类似后续遍历
//{
//    if(left>=right)//代表已经不能在分了
//    {
//        return;
//    }
//
//    int middle=(left+right)/2;//中间值
//    //[left middle][middle+1 right]
//    _MergeSort(a,tmp,left,middle);//左半区间
//    _MergeSort(a,tmp,middle+1,right);//右半区间
//
//    int began1=left,end1=middle;//左边区间
//    int began2=middle+1,end2=right;//右边区间
//
//    int index=left;
//    //一个循环
//    while(began1<=end1&&began2<=end2)
//    {
//        if(a[began1]<=a[began2])
//        {
//            tmp[index++]=a[began1++];
//        }
//        else
//        {
//            tmp[index++]=a[began2++];
//        }
//    }
//
//
//
//    while(began1<=end1)
//    {
//        tmp[index++]=a[began1++];
//    }
//    while(began2<=end2)
//    {
//        tmp[index++]=a[began2++];
//    }
//
//    for(int i =left;i<=right;i++)
//    {
//        a[i]=tmp[i];
//    }
//
//
//
//
//}
//void MergeSort(int* a, int n)
//{
//    int *tmp= (int*)malloc(sizeof(int)*n);//交换需要的空间
//    _MergeSort(a,tmp,0,n-1);
//}



void MergeSortR(int *a,int n)
{
    int *tmp=(int *)malloc(sizeof(int )*n);
    int GroupNumb=1;
    while(GroupNumb<n)
    {
        for(int i =0;i< n ;i+=GroupNumb*2)
        {
            //直接控制下标
            int began1=i,end1=i+GroupNumb-1;//左边区间
            int began2=i+GroupNumb,end2=i+(GroupNumb*2)-1;//右边区间

            //可能是基数个的时候会越界访问，重制
            if(end1>=n)
            {
                end1=n-1;
            }
            if(end2>=n)
            {
                end2=n-1;
            }

            int index=began1;
            //一个循环
            while(began1<=end1&&began2<=end2)
            {
                if(a[began1]<=a[began2])
                {
                    tmp[index++]=a[began1++];
                }
                else
                {
                    tmp[index++]=a[began2++];
                }
            }
            while(began1<=end1)
            {
                tmp[index++]=a[began1++];
            }
            while(began2<=end2)
            {
                tmp[index++]=a[began2++];
            }
        }
        for(int i =0;i<n;i++)
        {
            a[i]=tmp[i];
        }
        GroupNumb*=2;
    }

}
int main()
{

    int arr[]={9,78,73,2,5,59,3,6,91};
//    QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);
       MergeSortR(arr,sizeof(arr)/sizeof(arr[0]));
       Printf(arr,sizeof(arr)/sizeof(arr[0])-1);
}